// 08-图7 公路村村通

#include <stdio.h>
#include <stdlib.h>

/* Array ==============================================*/
int **init2D(int n) {
    int** a = (int**) calloc(sizeof(int*), n);
    for (int i=0; i<n; i++) {
        a[i] = (int*) calloc(sizeof(int), n);
    }
    return a;
}

void free2D(int **a, int n) {
    for (int i=0; i<n; i++) {
        free(a[i]);
    }
    free(a);
}

void print2D(int **m, int n, int defaultWeight) {
    for (int i=-1; i<n; i++) {
        printf("[%3d]", i);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        printf("[%3d]", i);
        for (int j=0; j<n; j++) {
            if (m[i][j] == defaultWeight) {
                printf("    -");
            } else {
                printf("%5d", m[i][j]);
            }
        }
        printf("\n");
    }
}

/* MGraph =============================================*/

// 定义权重的最大值
#define MaxWeight 0x7FFF
// 无路径
#define Connectionless -1
// 有向图, 无向图
#define DirectedGraph 1
#define UndirectedGraph 0

// 权重类型
typedef int WeightType;
typedef struct Edge Edge;
struct Edge {
    int v, w;
    WeightType weight;
};

typedef struct MGraph MGraph;
struct MGraph {
    int directed; // 1-有向图，0-无向图
    int defaultWeight; // 默认的无连接的权重
    int vertexNum; // 顶点数
    int edgeNum;   // 边数
    WeightType **g; // 邻接矩阵
};

Edge createEdge(int v, int w, int weight) {
    Edge e;
    e.v = v;
    e.w = w;
    e.weight = weight;
    return e;
}

MGraph *createGraph(int directed, int defaultWeight, int vertexNum) {
    MGraph* g = (MGraph*)calloc(sizeof(MGraph), 1);
    g->directed = directed;
    g->defaultWeight = defaultWeight;
    g->vertexNum = vertexNum;
    // 初始化邻接矩阵
    g->g = (WeightType**) malloc(sizeof(WeightType*) * vertexNum);
    for (int v=0; v < g->vertexNum; v++) {
        g->g[v] = (WeightType*) malloc(sizeof(WeightType) * vertexNum);
        for (int w=0; w < g->vertexNum; w++) {
            g->g[v][w] = defaultWeight;
        }
    }
    return g;
}

void freeGraph(MGraph* g) {
    free2D(g->g, g->vertexNum);
    free(g);
}

// 判断图的两个顶点 v1, v2 之间是否有直接连接
int isConnection(MGraph* g, int v1, int v2) {
    return g->g[v1][v2] != g->defaultWeight;
}

void insertEdge(MGraph* g, int v1, int v2, WeightType weight) {
    g->g[v1][v2] = weight;
    if (g->directed == UndirectedGraph) {
        g->g[v2][v1] = weight;
    }
}

void printGraph(MGraph* g) {
    printf("Graph n=%d, e=%d\n", g->vertexNum, g->edgeNum);
    print2D(g->g, g->vertexNum, g->defaultWeight);
}
// #include "../base/MGraph-Prim.c"
/* 邻接矩阵存储 - Prim最小生成树算法 */
/* 返回未被收录顶点中dist最小者 */
int findMinDist(MGraph *graph, WeightType dist[] ) { 
    int minV = -1; // 默认顶点不存在，-1作为标记
    WeightType minDist = MaxWeight;

    for (int v=0; v < graph->vertexNum; v++) {
        if (dist[v] != 0 && dist[v] < minDist) {
            /* 若V未被收录，且dist[V]更小 */
            minDist = dist[v]; /* 更新最小距离 */
            minV = v; /* 更新对应顶点 */
        }
    }
    return minV;
}

/* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
int prim(MGraph *graph, MGraph *MST) { 
    // dist[v] == 0, 表示 v 已收录
    WeightType *dist = (WeightType*) calloc(graph->vertexNum, sizeof(WeightType));
    int *parent = (int*) calloc(graph->vertexNum, sizeof(int));
    /* 初始化。默认初始点下标是0 */
    for (int v=0; v < graph->vertexNum; v++) {
        /* 这里假设若V到W没有直接的边，则Graph->G[v][w]定义为MaxWeight */
        dist[v] = graph->g[0][v];
        parent[v] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ 
    }
    WeightType totalWeight = 0; /* 初始化权重和     */
    
    /* 将初始点0收录进MST */
    dist[0] = 0;
    int vCount = 1;     /* 初始化收录的顶点数 */
    parent[0] = -1;     /* 当前树根是0 */
    // printf("收录 %d, parent[%d]=%d\n", 0, 0, parent[0]);
    while (1) {
        int v = findMinDist(graph, dist);
        // printf("未被收录顶点中dist最小者: v=%d\n", v);
        /* V = 未被收录顶点中dist最小者 */
        if (v == -1) /* 若这样的V不存在 */
            break;   /* 算法结束 */
            
        /* 将V及相应的边<parent[V], V>收录进MST */
        int v1 = parent[v];
        int v2 = v;
        WeightType weight = dist[v];
        insertEdge(MST, v1, v2, weight);
        totalWeight += dist[v];
        dist[v] = 0;
        vCount++;
        
        for(int w=0; w < graph->vertexNum; w++) {
            /* 对图中的每个顶点W */
            if (dist[w]!=0 && graph->g[v][w] < MaxWeight) {
                /* 若W是V的邻接点并且未被收录 */
                if (graph->g[v][w] < dist[w]) {
                    /* 若收录V使得dist[w]变小 */
                    dist[w] = graph->g[v][w]; /* 更新dist[w] */
                    parent[w] = v; /* 更新树 */
                }
            }
        }
    } /* while结束*/
    if (vCount < graph->vertexNum) {
        /* MST中收的顶点不到|V|个 */
       totalWeight = -1;
    }
    free(dist);
    free(parent);
    return totalWeight;   /* 算法执行完毕，返回最小权重和或错误标记 */ 
}

/* current =============================================*/
void readEdgeV1WithWeight(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        WeightType dist;
        scanf("%d %d %d", &v1, &v2, &dist);
        insertEdge(g, --v1, --v2, dist);
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    MGraph* g = createGraph(UndirectedGraph, MaxWeight, n);
    readEdgeV1WithWeight(g, m);
    // printGraph(g);

    MGraph* mst = createGraph(UndirectedGraph, MaxWeight, g->vertexNum);
    // 计算
    int totalWeight = prim(g, mst);
    printf("%d\n", totalWeight);
    // printf("mst\n");
    // printGraph(mst);

    freeGraph(g);
    freeGraph(mst);
    return 0;
}
